package array;

import java.util.HashSet;
import java.util.Set;

/**
 * 给你一个下标从 0 开始的整数数组 nums 。
 * 如果一个前缀 nums[0..i] 满足对于 1 <= j <= i 的所有元素都有 nums[j] = nums[j - 1] + 1 ，那么我们称这个前缀是一个 顺序前缀 。
 * 特殊情况是，只包含 nums[0] 的前缀也是一个 顺序前缀 。
 * 请你返回 nums 中没有出现过的 最小 整数 x ，满足 x 大于等于 最长 顺序前缀的和。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,3,2,5]
 * 输出：6
 * 解释：nums 的最长顺序前缀是 [1,2,3] ，和为 6 ，6 不在数组中，所以 6 是大于等于最长顺序前缀和的最小整数。
 * 示例 2：
 * <p>
 * 输入：nums = [3,4,5,1,12,14,13]
 * 输出：15
 * 解释：nums 的最长顺序前缀是 [3,4,5] ，和为 12 ，12、13 和 14 都在数组中，但 15 不在，所以 15 是大于等于最长顺序前缀和的最小整数。
 *
 * @author jishenghuang
 * @version 20250409
 */
public class SmallestMissingIntGTThanSeqPrefixSum_2996 {
    /**
     * 求出最长前缀，同时维护最长前缀的元素和 sum。
     * 不断增加 sum，直到 sum 不在 nums 中。
     * 返回 sum。
     *
     * @param nums the given integer array
     * @return the sum of the consecutive prefix
     */
    public static int missingInteger(int[] nums) {
        int sum = nums[0];

        for (int i = 1; i < nums.length && nums[i] == nums[i - 1] + 1; ++i) {
            sum += nums[i];
        }

        Set<Integer> set = new HashSet<>();

        for (int num : nums) {
            set.add(num);
        }

        while (set.contains(sum)) {
            ++sum;
        }

        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 2, 5};

        System.out.println(missingInteger(nums));

        nums = new int[]{3, 4, 5, 1, 12, 14, 13};

        System.out.println(missingInteger(nums));
    }
}
